import java.util.LinkedList;

/**
 * 232. 用栈实现队列
 * https://leetcode-cn.com/problems/implement-queue-using-stacks/
 */
public class Solutions_232 {
    public static void main(String[] args) {
        MyQueue_232 obj = new MyQueue_232();
        obj.push(1);
        obj.push(2);

        int res1 = obj.peek();  // output: 1
        System.out.println(res1);
        int res2 = obj.pop();  // output: 1
        System.out.println(res2);
        boolean res3 = obj.empty();  // output: false
        System.out.println(res3);
    }
}

class MyQueue_232 {
    LinkedList<Integer> stack;
    LinkedList<Integer> stack2;

    public MyQueue_232() {
        stack = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void push(int x) {
        stack.push(x);
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (stack2.isEmpty()) {
            toStack2();
        }
        return stack2.pop();
    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        if (stack2.isEmpty()) {
            toStack2();
        }
        return stack2.peek();
    }

    /**
     * 将 stack 中的元素，转移到 stack2 中
     * 按照栈的先进后出原则，那么 stack 的栈顶元素，成了 stack2 中的栈底元素
     * 如此便实现了先进先出
     */
    public void toStack2() {
        while (!stack.isEmpty()) {
            stack2.push(stack.pop());
        }
    }

    public boolean empty() {
        return stack.isEmpty() && stack2.isEmpty();
    }
}
